package com.wtgroup.demo.mianshi.算法.排序2305;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/1 19:22
 */
public class CountSort {

    public static void main(String[] args) {
        Judger.of(() -> {
            int[] nums = RandomUtil.randomArray((int) (Math.random() * 1000 + 1), -100, 100);
            int[] copy1 = Arrays.copyOf(nums, nums.length);
            new CountSort().sort(copy1);

            int[] copy2 = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy2);

            if (!Tools.equals(copy1, copy2)) {
                Tools.printArray(nums);
                Tools.printArray(copy1);
                Tools.printArray(copy2);
                return false;
            }
            return true;
        }).setIterCount(1000).start().print();
    }

    void sort(int[] arr) {
        int[] mm = getMaxMin(arr);
        int min = mm[0], max = mm[1];
        int[] bucket = new int[max - min + 1];
        // System.out.println(countArr.length);

        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i] - min]++;
        }

        // 回填
        for (int j = 0, i = 0; j < bucket.length; j++) {
            int count = bucket[j];
            while (count-- > 0) {
                arr[i++] = min + j;
            }
        }
    }

    private int[] getMaxMin(int[] arr) {
        int min = arr[0], max = min;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            } else if (arr[i] > max) {
                max = arr[i];
            }
        }
        return new int[]{min, max};
    }
}
